package RealTim0;

// TODO 动态规划 | 贪心算法 [经典] 【-】 最长上升子序列(一)
// TODO https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f

public class xqz0001 {

    public int LIS (int[] arr) {
        int n = arr.length;
        if (n == 0 || n == 1) {
            return n;
        }

        // dp[i] 表示 以第i个位置为结尾 的 最长上升子序列
        int[] dp = new int[n];
        int max = 0;

        // 初始状态
        dp[0] = 1;
        dp[1] = arr[1] > arr[0] ? 2 : 1;

        // 状态转移
        for (int i=2; i<n; i++) {
            dp[i] = 1;
            for (int j=i-1; j>=0; j--) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(max, dp[i]);
                }
            }
        }

        return max;
    }

}
